// https://www.lintcode.com/problem/193/
class Solution {
public:
    /**
     * @param s: a string
     * @return: return a integer
     */
     // 法一：栈 O(n)
    // 解法一
    // int longestValidParentheses(string s) {
    //     stack<int> char_stack; //存放左括号的下标
    //     int max_length = 0;
    //     int len = 0;
    //     int total_len = 0;
    //     for (int i = 0; i < s.length(); ++i) {
    //         if (s[i] == '(') {
    //             char_stack.push(i);
    //         } else {
    //             if (char_stack.empty()) {
    //                 total_len = 0;
    //             } else {
    //                 int tmp = char_stack.top();
    //                 char_stack.pop();
    //                 len = i - tmp + 1;
    //                 // total_len += len; ()(()) 会重复加
    //                 if (char_stack.empty()) {
    //                     total_len += len;
    //                     len = total_len;
    //                 } //(()); )()())
    //                 else {
    //                     // max_length = max(max_length, len); (()()
    //                     len = i - char_stack.top(); 
    //                     // 直接更新成当前元素和栈顶元素的距离，中间都是匹配掉的
    //                     // 不要更新total，(()())
    //                 }
    //                 max_length = max(max_length, len);
    //             } 
    //         }
    //     }
    //     return max_length;
    // }

    // 解法二
    // 用 start 记录一个新的可能合法的子串的起始位置
    // https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zhan-zui-jian-jie-yi-dong-de-dai-ma-cjav-xa7v/
    // int longestValidParentheses(string s) {
    //     stack<int> char_stack; //存放左括号的下标
    //     int start = 0;
    //     int ans = 0;
    //     for (int i = 0; i < s.length(); ++i) {
    //         if (s[i] == '(') char_stack.push(i); 
    //         else {
    //             if (!char_stack.empty()) {
    //                 char_stack.pop();
    //                 if (char_stack.empty()) {
    //                     ans = max(ans, i - start + 1);
    //                 } else {
    //                     ans = max(ans, i - char_stack.top());
    //                 }
    //             } else {
    //                 start = i + 1;
    //             }
    //         }
    //     }
    //     return ans;
    // }

    // 法二：dp O(n)
    // https://leetcode-cn.com/problems/longest-valid-parentheses/solution/dong-tai-gui-hua-si-lu-xiang-jie-c-by-zhanganan042/
    int longestValidParentheses(string s) {
        int n = s.length();
        vector<int> rec(n, 0);
        int max_length = 0;
        if (n < 2) return 0;
        if (s[0] == '(' && s[1] == ')') {
            rec[1] = 2;
            max_length = 2; //注意
        }
        for (int i = 2; i < n; ++i) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    rec[i] = rec[i - 2] + 2;
                } else if (rec[i - 1] > 0) {
                    if (i - rec[i - 1] - 1 >= 0 && s[i - rec[i - 1] - 1] == '(') {
                        rec[i] = rec[i - 1] + 2;
                        // dp[i−dp[i−1]−2]要加上，(...)(...)这种
                        if (i - rec[i - 1] - 2 >= 0) {
                            rec[i] = rec[i] + rec[i - rec[i - 1] - 2];
                        }
                    }
                }
            }
            max_length = max(max_length, rec[i]);  
        }
        return max_length;
    }
};